1. Field of the Invention
The invention relates in general to a decoding technique, and more particularly to a technique for optimizing efficiency of Huffman decoding.
2. Description of the Related Art
Huffman coding is a prevalent data compression technique in modern multimedia systems. A principle concept of the Huffman coding is that, the coding corresponding to a source symbol is determined according to an estimated probability of the occurrence of each source symbol in a stream of symbols to be compressed—a source symbol with higher probability of occurrence is given a shorter code, while another source symbol with lower probability of occurrence is given a longer code. A relationship between symbols and corresponding codes can be observed in a Huffman tree. Each coded codeword comprises a path data for indicating where the symbol corresponding to the codeword locates in the Huffman tree. A receiving end system then decodes received data according to the known Huffman tree.
Using an arbitrary prior art Huffman tree in FIG. 1 as an example, each leaf node, depicted as a block at a lowest terminal, denotes a symbol, and a code corresponding to each symbol is marked along a path between a root node and the leaf node. In this example, the code of a symbol 1 is 000, the code of a symbol 0 is 001, the code of a symbol 2 is 01, and so forth.
Under certain circumstances, to simplify the hierarchical structure of the Huffman tree, a coding system defines a plurality of source symbols having lower probabilities of occurrence as rare codes, and incorporates the rare codes in a single symbol (the symbol 0 is to be taken as an example below). In the prior art, each time a codeword is received, the decoding system searches bit by bit, from top to bottom, from the root node of the Huffman tree according to the path data of the codeword until the leaf node corresponding to the path data is identified. Supposing the symbol of the identified leaf node is 0, the decoder then performs a rare code decoding procedure on the codeword to retrieve the source symbol. Conversely, supposing the codeword is not a rare code, the decoding system directly regards the symbol identified according to the path data as a decoded result.
However, it remains a drawback in the prior art that, the decoding system is unable to determine whether a codeword is a rare code until fully tracking to a leaf node to identify that the codeword is corresponding to the symbol 0. The process for determining whether a codeword is a rare code is particularly time consuming for a Huffman tree having large or complicated hierarchies.